package Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class FirstGraphTest {
    private List<String> dingdian;
    private int [][]edges;
    private int numberOfEdeg;
    private boolean [] isTrue;
    public static void main(String[] args) {

        String[] strings = {"A","B","C","D","E"};
        FirstGraphTest s = new FirstGraphTest(strings.length);
        for (int i = 0; i < strings.length ; i++) {
            s.insert(strings[i]);
        }
        s.addEdge(0,1,1);
        s.addEdge(0,2,1);
        s.addEdge(1,2,1);
        s.addEdge(1,3,1);
        s.addEdge(1,4,1);
        s.showEdges();

//        s.dnf();
//        System.out.println("111");
        s.bfs();
//        System.out.println(111);
    }

    public FirstGraphTest(int n) {
        edges = new int[n][n];
        dingdian = new ArrayList<>(n);
        isTrue = new boolean[n];
    }

    //插入节点
    public void insert(String v){
        dingdian.add(v);
    }
    //获取节点的个数
    public int getNumberOfDingdian(){
        return dingdian.size();
    }
    //获取节点通过索引
    public String getDingdian(int i){
        return dingdian.get(i);
    }
    //获取边的个数
    public int getNumberOfEdeg(){
        return numberOfEdeg;
    }
    //添加边
    public void addEdge(int v1,int v2, int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        numberOfEdeg++;
    }
    //遍历：
    public void showEdges(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }
    public int getFirst(int index){
        for(int i = 0 ; i < dingdian.size();i++){
            if (edges[index][i]>0){
                return i;
            }
        }
        return -1;
    }
    public int getNext(int v1,int v2){
        for (int i = v2+1 ;i<dingdian.size();i++){
            if(edges[v1][i]>0){
                return i;
            }
        }
        return -1;
    }
    private void dnf(boolean [] isTrue,int i ){
        System.out.print(getDingdian(i)+"-->");
        isTrue[i]=true;
        int w = getFirst(i);
        while (w!=-1){
            if (!isTrue[w]){
                dnf(isTrue,w);
            }
            w = getNext(i,w);
        }
    }
    public void dnf(){
        for (int i = 0 ; i < dingdian.size() ; i++){
            if(!isTrue[i]){
                dnf(isTrue,i);
            }
        }
    }
    //对一个节点进行广度优先遍历
    private void bfs(boolean [] isTrue,int i){
        int u;//队列头结点
        int w;//下一个节点
        LinkedList queue = new LinkedList();
        System.out.print(getDingdian(i)+"-->");
        isTrue[i]=true;
        queue.addFirst(i);
        while (!queue.isEmpty()){
           u = (int) queue.removeFirst();
           w = getFirst(u);
            while (w!=-1){
                if (!isTrue[w]){
                    System.out.print(getDingdian(w)+"-->");
                    isTrue[w]=true;
                    queue.addLast(w);
                }
                w = getNext(u,w);
            }
        }
    }
    public void bfs(){
        for (int i = 0; i < dingdian.size(); i++) {
            if(!isTrue[i]){
                bfs(isTrue,i);
            }
        }
    }
}
